BZOJ1087【SCOI2005】互不侵犯King <状压DP>

Problem

【SCOI2005】互不侵犯King

Description

在的棋盘里面放个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共个格子。

Input

只有一行，包含两个数, (, )

Output

方案数。

Sample Input

3 2

Sample Output

标签：状压DP

Solution

状压的基础题。
对于每个国王，不难发现它放与不放只与当行和前一行有关，而它放完后的影响只作用于当行和后一行。
而
于是考虑状压，表示当前考虑到第行，共用了个国王，第行状态为的方案数。那么和前一行的状态是否冲突可以用、、与取得到。时间复杂度。

Code

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long lnt;
int n, k, cnt[100], sta[1000], tot;
lnt f[10][1000][1000], ans;	bool mrk[1000];
void init() {
    for (int i = 0; i < (1<<n); i++) {
        if (i&(i<<1))	continue;
        mrk[i] = true, sta[tot++] = i;
        for (int j = i; j; j >>= 1)	cnt[i] += (j&1);
        f[1][cnt[i]][i] = 1;
    }
}
int main() {
    scanf("%d%d", &n, &k), init();
    for (int i = 2; i <= n; i++)	for (int j = 0; j <= k; j++)	for (int p = 0; p < tot; p++) {
        int cur = sta[p];	if (cnt[cur] > j)	continue;
        for (int q = 0; q < tot; q++) {
            int lst = sta[q];
            if ((cur&lst) || ((cur<<1)&lst) || ((cur>>1)&lst))	continue;
            f[i][j][cur] += f[i-1][j-cnt[cur]][lst];
        }
    }
    for (int i = 0; i < tot; i++)	ans += f[n][k][sta[i]];
    printf("%lld", ans);
    return 0;
}